L2-013 红色警报

题目 L2-013 红色警报

思路分析

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};

const int inf = 0x3f3f3f3f;

const int N=505;

bool g[N][N];

bool st[N];

bool banned[N];

int n,m;

void bfs(int u){

	queue<int> q;

	q.push(u);

	st[u]=true;

	while(!q.empty()){

		int t=q.front();q.pop();

		for(int v=0;v<n;v++){

			if(!banned[v] && g[t][v] && !st[v]){

				st[v]=true;

				q.push(v);

			}

		}

	}

}

int countBolcks(){

	memset(st,0,sizeof st);

	int cnt=0;

	for(int i=0;i<n;i++){

		if(!banned[i] && !st[i]){

			bfs(i);

			cnt++;

		}

	}

	return cnt;

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m;

	for(int i=0;i<m;i++){

		int a,b;cin>>a>>b;

		g[a][b]=g[b][a]=true;

	}

	int k;cin>>k;

	int currentBlocks = countBolcks();

	for(int i=0;i<k;i++){

		int city;cin>>city;

		banned[city]=true;

		int newBlocks = countBolcks();

		if(newBlocks <= currentBlocks){

			cout << "City " << city << " is lost." << endl;

		}else if(newBlocks > currentBlocks){

			cout << "Red Alert: City " << city << " is lost!" << endl;

		}

		currentBlocks=newBlocks;

		if(i==n-1){

			cout << "Game Over." << endl;

		}

	}

	return 0;

 }

同类题型

视频讲解

⬅️ L2-012 关于堆的判断 🏠 00-天梯赛 ➡️ L2-014 列车调度